package leetcode_161_180;

public class calculateMinimumHP_174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int row=dungeon.length,column=dungeon[0].length;
        int [][]blood_reminder_need=new int[row][column];   //到达该位置，至少需要剩下多少血量才能到达终点
        for (int i=row-1;i>-1;i--){     //从后往前遍历
            for (int j=column-1;j>-1;j--){
                //当前格子加或减血量值
                int blood=dungeon[i][j];
                //最后一个格子的特殊情况
                if(i ==row-1 && j ==column-1){
                    blood_reminder_need[i][j]=blood>0?0:-blood;
                    continue;
                }
                //向下走需要血量
                // 最后一行的元素特殊情况，不用考虑往下的方向(将向下的方向所需血量设为无限大
                int blow = ( i != row - 1 ) ? blood_reminder_need[i + 1][j] : Integer.MAX_VALUE;
                //向右走需要血量
                int right = ( j != column - 1 ) ? blood_reminder_need[i][j + 1] : Integer.MAX_VALUE;
                // 比较向右走和向左走，哪个需要的血量更低
                // 如果从该位置走最佳路线走需要的最终血量 < 0，按0算，不影响往前推算实时血量
                blood_reminder_need[i][j] = Math.max(Math.min(right, blow)- blood, 0) ;
            }
        }
        //最低初始健康点数为1
        return blood_reminder_need[0][0]+1;
    }
}
